perm filename D2[IJ,DBL] blob
sn#131989 filedate 1974-11-24 generic text, type T, neo UTF8
00100 .DEVICE XGP
00200
00300 .FONT 1 "NGR25"
00400 .FONT 2 "NGB25"
00500 .FONT 3 "NGR20"
00600 .FONT 4 "BDI25"
00700 .FONT 5 "NGB30"
00800 .FONT 6 "FIX20"
00900 .FONT 8 "FIX25"
01000 .TURN ON "↓_π{"
01100 .TURN ON "⊗" FOR "%"
01200 .MACRO B ⊂ BEGIN VERBATIM GROUP ⊃
01300 .MACRO E ⊂ APART END ⊃
01400 .TABBREAK
01500 .COMPACT
01600 .SELECT 1
00100 .PAGE FRAME 43 HIGH 82 WIDE
00200 .AREA TEXT LINES 1 TO 43
00300 .!XGPLFTMAR←190
00400 .NOFILL
00500 .PAGE FRAME 43 HIGH 82 WIDE
00600 .AREA TEXT LINES 1 TO 43
00700 .!XGPLFTMAR←190
00800 .FILL
00900 .SPACING 70 MILLS
01000 .PREFACE 200 MILLS
01100 .NEXT PAGE
01200 .BEGIN CENTER
01300 ⊗5 BEINGS: REPRESENTATION OF KNOWLEDGE AS INTERACTING MODULES⊗*
01400
01500 Douglas B. Lenat
01600 Stanford Artificial Intelligence Laboratory
01700 Stanford, California
01800
01900 ⊗5↓_ABSTRACT_↓⊗*
02000
02100 .END
02200
02300 .INDENT 6
02400
02500 Knowledge, including that of control, may be organized as a
02600 community of interacting modules (e.g., ACTORS). By granting each
02700 module a complex structure, complex behaviors are easily elicited. By
02800 constraining that this structure be standard over the entire
02900 community, the advantages of a uniform formalism are preserved.
03000 Several task domains are considered; the most natural is seen to
03100 be automatic programming. An experimental system was partially
03200 implemented for this task. It has managed to synthesize
03300 a few inductive
03400 inference LISP programs heuristically, from specific restricted
03500 dialogues. This research clarified some difficulties inherent to
03600 structured modular systems.
00100
00200 .B
00300
00400 .E
00500 .ONCE CENTER
00600 ⊗5↓_1. INTRODUCTION_↓⊗*
00700
00800 This paper reports on a scheme for representing knowledge as a pool of
00900 structured units, called BEINGs. Each module has several ⊗4parts⊗*, each of
01000 which is either ⊗4primitive⊗* or a pointer to another BEING. The name of
01100 a BEING part represents a question one expert might want to ask another; the
01200 value of the part is that BEING's answer to that question. Thus the parts
01300 correspond to the messages in the ACTOR [1] formalism. A new constraint is
01400 introduced here, however: every BEING has the same set of parts (with
01500 distinct values, of course).
01600 This uniformity was hoped to permit easy addition of new BEINGs to the pool,
01700 and to facilitate communication among the BEINGs.
01800
01900 A small community of BEINGs was formed, aimed at generating LISP programs
02000 from dialogues with a human user. This experimental system, PUP6, was not
02100 a formal automatic programming program, but rather used the BEINGs to
02200 organize informal knowledge about programming, about the task domain
02300 (inductive inference), and about transfer of control. Three programs have
02400 actually been synthesized by PUP6:
02500 a concept formation program (similar to [2]),
02600 a grammatical inference program, and a simple property list maintenance
02700 routine (referred to below as CF, GI, and PL, respectively). Specification
02800 is via rigid dialogue, carried on at great length with the user, in a
02900 small subset of English, in which the task is delineated and
03000 questionable details are discussed. The specification is partial
03100 (ambiguous); the system makes assumptions continually. This process
03200 will be referred to as ⊗4automatic programming.⊗* The code which has
03300 been successfully generated is called the ⊗4target program⊗*.
03400 The main successes of PUP6 were that the desired reasoning
03500 steps in the original human-programmer
03600 protocol were actually simulated, most of the BEINGs
03700 were called on in writing all three programs, and a new "style" of target
03800 program was discovered (the user can interrupt and pose questions, just as
03900 he can with the original pool of BEINGs).
04000 The main
04100 defects were pup6's inflexibility to new dialogues, the
04200 inability of an untrained user to add new BEINGs, and the verbosity of the
04300 system.
04400
04500 Our treatment will follow these lines:
04600 First, the ideas of the BEINGs scheme are presented. Examples are then
04700 supplied to illustrate these concepts. The specific
04800 implementation in the domain of automatic programming is
04900 sketched.
05000 Some of its difficulties are shown
05100 to reflect on the BEINGs ideas themselves.
05200
00100
00200 .B
00300
00400 .E
00500 .ONCE CENTER
00600 ⊗5↓_2. General BEING System Ideas_↓
00700
00800 How should knowledge be represented? Many researchers feel
00900 that a simple, uniform formalism should be used for all facts; others
01000 disagree, claiming that complexity of behavior both justifies and
01100 demands complexity of representation.
01200 The benefits of the former include easy
01300 addition of knowledge [3] and simple, aesthetic methods for
01400 communicating and combining information [4].
01500 Structure, however, is necessary
01600 for (⊗4combinatorially⊗*) efficient handling of large amounts of data
01700 (see the real world; also
01800 [5]).
01900 A BEING is a collection of several little bits of procedural
02000 code; the answers to questions about the BEING.
02100 That is, a BEING is a small, loosely-knit program, which is
02200 considered ⊗4equivalent⊗* to its answers to these fixed questions. Every
02300 piece of knowledge, including those related to the flow of
02400 control in the system, should be encoded
02500 into BEINGs. There should be nothing else in the system but this
02600 interacting community.
02700 Thus BEINGs represent a compromise of structure and uniformity.
02800 While each BEING is highly structured, this
02900 structure is standard over the entire pool. Each BEING part is itself
03000 a little BEING, etc., and this infinite regress stops when the
03100 contents of a BEING part becomes sufficiently primitive.
03200 The BEINGs operate at about the same level as a
03300 human performing the same task;
03400 BEINGs should consider as primitive just what he considers primitive.
03500 For example, in the automatic programming task (AP), this level
03600 was typically the same as the INTERLISP [6]
03700 language: a primitive was a single INTERLISP function
03800 call, or a few simple ones connected trivially. Each BEING is
03900 cognizant of the set of thirty questions, in the sense that in
04000 answering one of them it may freely ask questions of other BEINGs
04100 (often through nondeterministic goal statements). A few of the
04200 BEING-PARTS for AP might be: what is your basic idea and purpose, what
04300 effects do you have, how do you cause them, what must be
04400 ensured before you begin, what is your
04500 chance of success, whom else might you transfer
04600 control to, what alternatives to you exist,
04700 do you evaluate your arguments, what
04800 is the nature of the value you return, why do you
04900 want to be in control now, etc.
05000 The delineation of this set of questions has much to do with
05100 the epistemology of programming.
05200 Each BEING part has two abilities: it may be
05300 ⊗4asked⊗* about something, and it may be ⊗4called⊗* on to do
05400 something. Each of these may involve asking and calling other parts
05500 of itself and of other BEINGs, but typically the second activity
05600 involves an extra level of evaluation.
05700 For example, the ARGS part may be asked simple
05800 questions about the arguments to the BEING, and it is charged with
05900 binding the arguments when the BEING is given control.
06000 The BEINGs control themselves in a simple way. A very general
06100 BEING, SERVE-THE-USER, has control initially. In general, some BEING
06200 ⊗4B⊗* will be in control. Its BEING parts are assembled into an
06300 executable function, and it is run. During the course of its reign,
06400 ⊗4B⊗* will want things done and/or tested which it cannot manage by
06500 itself. This corresponds to when a normal program needs to call a
06600 subroutine. What ⊗4B⊗* does is to call on SATISFY, a BEING which
06700 is the system's general goal mechanism. All it need do is accept a
06800 description of what is needed, then ask the entire pool "who can
06900 do this?" Another general BEING, CHOOSE-FROM, then ranks those which
07000 respond. These two "special" BEINGs seem
07100 to detract from the equality
07200 proclaimed earlier for all BEINGs. But the mechanism for goal
07300 satisfaction and for choosing among vying BEINGs is standard; either
07400 it must be duplicated inside every BEING or else factored out into
07500 some higher-level (meta-, interaction-) BEINGs.
07600 Similarly, the way a BEING's parts fit together
07700 is uniform over all the BEINGs at all times. Thus one simple function
07800 (or assembled BEING; see 3.3) can assemble all the BEINGs initially
07900 into LISP functions.
08000 BEINGs are the only entities permitted (theoretically) to
08100 exist in our system; ergo, for the AP task, all the synthesized code
08200 must be written as BEINGs, and
08300 must be written by BEINGs.
08400 An obvious but crucial consequence is that ⊗4some⊗* BEING(s)
08500 must write new BEINGs. The significant design decision was
08600 that the BEING who knows about
08700 ⊗4X⊗* takes charge of generating BEINGs relating to ⊗4X⊗*. For
08800 example, the INSERT BEING can do inserting by one of a few
08900 algorithms, he can write (by specializing himself) more
09000 efficient, special-purpose insert routines,
09100 and he can answer thirty questions about
09200 inserting. This idea is analogous to any reliance upon experts
09300 [7], and also reemphasizes the theme of any modular
09400 representation of knowledge.
09500 A second consequence is that the synthesized code will be BEINGs, hence
09600 possess all the ⊗4types⊗* of "intelligence" that the original BEINGs
09700 community had (modify itself according to the user's
09800 complaints, answer questions about what it is doing as it runs).
09900 In a similar vein, ⊗4some⊗* BEING(s) must do the translation
10000 of the users' quasi-English inputs into BEING-usable form. ↓_Each_↓
10100 BEING ⊗4X⊗* must handle English phrases related to ⊗4X⊗*.
10200 Thus translation
10300 consists of querying "who can recognize ..." and waiting for a
10400 response. For example, our INSERT BEING must recognize and
10500 process phrases involving inserting, stack-pushing, and merging.
10600 A result of this processing of natural language
10700 is that any phrase which can be translated can be acted
10800 upon.
10900 Why is automatic programming (AP) a good task for a
11000 BEINGs pool?
11100 The BEINGs representation may be suitable for simulating any
11200 complex task ⊗4T⊗* involving frequent small interventions by various
11300 experts. In addition to writing programs, this activity could
11400 perhaps be as
11500 diverse as playing chess, coordinating sensors/effectors,
11600 simulating physical
11700 interactions, doing research in mathematics, or playing volleyball.
11800 Some of these will be elaborated in section 3.
11900 There ⊗4is⊗* one particular bias of BEINGs toward writing
12000 high-level programs, over other activities. The new BEINGs created
12100 during the execution of a specified task are kept distinct from the
12200 original set of BEINGs. Then a ⊗4program⊗* for task ⊗4T⊗* is
12300 accomplished by doing ⊗4T⊗* and then dumping the new BEINGs out onto
12400 a new file. The entire old BEINGs pool is then treated as the
12500 language supporting this file.
12600 Henceforth, the
12700 task for the BEINGs pool will be AP
12800 unless explicitly stated otherwise.
12900 A few of the "new ideas" may be disguised new biasses.
13000 These include lack of reverence toward the
13100 exploratory anthropomorphic paradigm (common to programming, doing math,
13200 etc.) of ignoring details and catching them
13300 later by debugging. As in all complex behavior,
13400 decisions continually crop up which
13500 no BEING is able to resolve at the time. The BEINGs system
13600 should always spend a significant effort to defer the decision as
13700 long as possible. When, at last, no progress can be made without its
13800 resolution, and if the system is still unsure, then either the user
13900 settles the question or else a backtrack point is reluctantly set up.
14000 Hopefully, by this time, some new information is present which
14100 enables the system to resolve the decision, thus reducing the amount
14200 of backtracking. If there are two or more decisions which can no
14300 longer be deferred, the system tackles first the one estimated to be
14400 the easiest (analogous to Occam's razor).
14500 Another prejudice is that most of the carelessness
14600 "bugs" can be eliminated through this deferral, feed-forward, and very
14700 precise record-keeping. Humans depend on their adaptability to
14800 compensate for limitations in their brain hardware
14900 [3], but there is no
15000 need for an ⊗4automatic⊗* programming system to do so. For example,
15100 when a list structure is first encountered, a BEING can record
15200 warnings that it is undefined, unaccessed,
15300 and so on. Each such worry is weighted and deferred, but not
15400 forgotten.
15500
15600 Most programmers intentionally augment their code to aid in
15700 later debugging, modification, and readability by humans. These aids
15800 are typically comments, summaries, over-generalized subroutines,
15900 optional print statements, and runtime statistics. Recently, the
16000 structure of the program itself has also been
16100 recognized as a powerful
16200 manipulable element, affecting the accessability of the code, not just
16300 its length or running time.
16400 Any program written as a pool of
16500 BEINGs is several times as long as a clean hand-coded version. This
16600 extra code, the parts of each new BEING which are superfluous, may be
16700 viewed as well-organized self-documentation. They should improve the
16800 debugging, expansion, and accessibility (to alien users) of the
16900 synthesized code.
17000 Some assertions are so meaningful to the user,
17100 that they should be stored in the code itself, even if they are
17200 only temporary. At any time, the user
17300 may look at a piece of code; the comments present ⊗4then⊗* are all
17400 assertions pertaining to that piece of code at that time.
17500 BEINGS may use comments at several different levels. At the
17600 lowest level, each comment is merely a unique token; it may be
17700 inserted, removed, or searched for. Slightly better, the BEINGs
17800 system can ask "is there a comment involving ...". For this purpose, a
17900 constrained syntax for the comments should be developed. Otherwise
18000 (as, unfortunately in PUP6) each new comment must be attended to
18100 ad hoc. Still higher level
18200 usage would be looking at a comment totally
18300 ignorant of it, and ⊗4translating⊗* it into something meaningful.
18400 By studying the difficulties of the implementations of the BEINGs
18500 ideas, isolating those due to poor programming from those due to
18600 poor ideas, enough may be learned to build the next system one
18700 qualitative step closer to the ideal.
18800 It is in this spirit that BEINGs
18900 are now contrasted against the concepts of ACTORs, CLASSes,
19000 and FRAMES, and that the PUP6 system is examined.
19100 ACTORS [1] provided the key concept of integrating
19200 uniformity of construction with sophistocation of behavior. There
19300 is a continuum, among modular knowledge schemes, of standardization of
19400 "message" types between modules. ACTORs have no restriction whatsoever
19500 on this format. Each module has its own, unique parts (types of
19600 answers). So each ACTOR must be aware of all the parts (message formats)
19700 of all the ACTORs it ever is going to communicate with.
19800 Adding a new module is thus conceptually intricate as
19900 well as practically difficult. CLASSes [8] have a few standard
20000 parts, and the modules are arranged in groups, each of which has its
20100 own additional types of parts. Thus a module can ask ⊗4any⊗* other module
20200 one of a few universal questions, and it can ask any module in its group
20300 an additional set of questions. If it is permitted to know about other
20400 groups' special parts, then the same adding problem recurs. If it is
20500 denied such knowledge, it cannot access much of the knowledge in the
20600 pool. If one requires a completely universal set of message types, then
20700 most of them may be irrelevant to most modules. This is the price which
20800 BEINGs pay. Later, it will be shown that this superfluity is real and is
20900 marginally tolerable. The most devastating criticism of striving for a
21000 universal set of module questions is that all this does is push all the
21100 non-uniformity down into the ⊗4values⊗* of these parts. The only retort is
21200 empirical: if a good partitioning of the questions can be found, then
21300 the internal structure of each part with the same name will be comparable,
21400 and the only communication necessary will be simple accessing of
21500 modules's parts (direct questioning).
21600
21700 FRAMES [9] seems superficially similar to BEINGs, and
21800 are so amorphous that they actually could subsume BEINGs. There is a
21900 deep difference of philosophy and of intended usage, however.
22000 FRAMES intentionally have default values already (with no processing)
22100 filled in for each frame, and replaced only when necessary.
22200 This is akin to automatic programming by blind debugging, but is
22300 antithetical to the fastidious bookkeeping BEINGs philosophy. As an
22400 example, consider the writing of a short, recursive
22500 LISP program (reverse, flatten, factorial, alternate, etc.)
22600 A human, consulting the proper frame in his head, knows to ignore the
22700 base step for a while, then fill it in, usually as ⊗4if NIL, then
22800 NIL⊗*. The
22900 human makes this default synthesis, tries out the program, and looks
23000 closer (to fill in this "slot" properly) only if something calls his
23100 attention to it (such as a LISP error message:
23200 NON-NUMERIC ARG ⊗4NIL⊗*, e.g., if what was really needed was the base
23300 step ⊗4if NIL, then 0⊗*).
23400 A BEINGs system would
23500 also defer working on the base step, but could -- and would -- place
23600 a note about that deferral into the assertional warning base. Before
23700 thinking it was finished, the system would attend to that note
23800 carefully. This is not a criticism of FRAMES:
23900 they are meant to model
24000 perception, BEINGs are not.
00100
00200 .B
00300
00400 .E
00500 .ONCE CENTER
00600 ⊗5↓_3. Specific Examples_↓
00700
00800 .B
00900
01000 .E
01100 .ONCE FLUSH LEFT
01200 ↓_3.1. The set of BEING parts used in the automatic programming task_↓
01300
01400 Below are listed the actual set of BEING parts which were used in the
01500 PUP6 system. The overall task for the BEINGs is to write programs --
01600 i.e., more BEINGs. Next to each part is a brief description, and
01700 the percentage of BEINGS in the
01800 system which actually needed to have this part.
01900
02000 .BEGIN NOFILL
02100 .FLUSH LEFT
02200
02300 ⊗2IDEN⊗* 54% How is this BEING referenced in English phrases? Implemented as productions.
02400 ⊗2ARGS⊗* 63% How many arguments? Which are optional? Are there any local variables?
02500 ⊗2ARG-CHECK⊗* 81% Predicates which examine each argument for suitability.
02600 ⊗2EVAL-ARGS⊗* 4% Which arguments are to be evaluated, and which quoted?
02700 ⊗2WHAT⊗* 82% A brief summary of the global purpose. Usually a template for an English sentence.
02800 ⊗2WHY⊗* 77% A justification of the BEING's existence. The caller explains here why it was called.
02900 ⊗2HOW⊗* 72% A summary of the methods the BEING intends to employ. Global strategies.
03000 ⊗2EFFECTS⊗* 27% What will probably be true after this BEING is through? What can it achieve?
03100 ⊗2WHEN⊗* 19% Why should this BEING be given control now? Computed as the sum of weighted factors.
03200 ⊗2META-CODE⊗* 70% The body of the executable code, but with uninstantiated subparts.
03300 ⊗2COMMENTS⊗* 16% Hints for filling in undefined sections of other BEING parts.
03400 ⊗2REQUISITES⊗* 10% If this BEING is actually chosen, what must be made true just before (pre-),
03500 during (co-), and after (post-) execution? Work to make these true (unlike ARG-CHECK).
03600 ⊗2DEMONS⊗* 7% Which demons should be kept active while the BEING is in control?
03700 ⊗2AFFECTS⊗* 14% Which other BEINGs might be called by this BEING, and why?
03800 ⊗2COMPLEXITY⊗* 92% A vector of utility measures, including ease of calling, chance of success, chance
03900 of (calling)* itself, expected time cost, efficiency of its output results.
04000 ⊗2SPECIALIZATIONS⊗* 40% How to write a more streamlined, special-case version of this BEING.
04100 ⊗2GENERALIZATIONS⊗* 27% What are some other BEINGs, encompassing this one?
04200 ⊗2ALTERNATIVES⊗* 16% What are some equivalent BEINGs? (to try if this one fails)
04300 ⊗2RESULTS⊗* 15% How many values does this return? What domain is each in? Any side effects?
04400 ⊗2STRUCTURE⊗* 4% If this is ever viewed as a data structure, what operations are done to it, and how?
04500 ⊗2ENCODABLE⊗* 9% How to order the evaluation of the other parts, when writing a new version.
04600 ⊗2INHIBIT-DEMONS⊗* 5% A lock/unlock mechanism, useful when handling demonic interrupts.
04700 .SELECT 1
04800
04900 ↓_3.2. A high-level domain-independent BEING_↓
05000
05100 .END
05200 OBTAIN-USABLE-INFORMATION is a typical high-level,
05300 domain-independent BEING. The WHEN part consists of a set of
05400 "⊗5if⊗* <predicate> ⊗5then⊗* <value> ⊗5because⊗* <reason>" expressions.
05500 If the <predicate> evals to non-null, then the <value> program is executed.
05600 It returns a number, which is
05700 .SKIP TO COLUMN 1
05800 .ONCE INDENT 0
05900 added in as a factor to the final WHEN
06000 value. The <reason> evaluates to a quasi-English phrase for inquisitive
06100 human users.
06200 The final sum reflects how good this BEING would be to pass control to.
06300 This "linear" scheme is undesirable, rough, but adequate.
06400 This particular BEING
06500 has factors which respond that it is ⊗4always⊗* an undesirable
06600 thing to do, but ⊗4may⊗* be indicated if there exists
06700 new but not yet usable information.
06800 These factors, and their weights (see below), like all the parts
06900 of all the BEINGs initially in PUP6, were decided upon and inserted by
07000 hand.
07100 The IDEN parts are collected together into a large
07200 translation table. When a form ⊗4X⊗* must be translated, the
07300 TRANSLATE BEING goes through this table, asking each IDEN part if it
07400 claims to recognize ⊗4X⊗*. Each IDEN runs its own little program,
07500 typically some type of pattern match involving ⊗4X⊗* and the state
07600 of the world, to answer this question.
07700 If there is more than one responder,
07800 CHOOSE-FROM picks the one with the highest priority of match. The
07900 winner runs a little program which ultimately returns a BEING-call or
08000 a constant as the translated value of ⊗4X⊗*. This program might call
08100 other BEINGs, often calls TRANSLATE several times recursively on
08200 parts of ⊗4X⊗*. Consider the IDEN part of the
08300 OBTAIN-USABLE-INFORMATION BEING (below).
08400 There are just two classes of phrases that this BEING can recognize.
08500 For example, the second usage is
08600 if some BEING or user wants to find out more about anything, then
08700 OBTAIN-USABLE-INFORMATION can be called with that thing as argument.
08800 The EFFECTS parts of each BEING are similarly collected into
08900 one table to facilitate asking all BEINGs simultaneously "Can you
09000 cause effect X to occur?" Each EFFECTS part examines X and the world, and
09100 either replies No, or else returns a little program (involving calls
09200 and constants) which should produce the effect, with a certain
09300 probability. This program generally will involve a call to the BEING
09400 itself. OBTAIN-USABLE-INFORMATION shows that it should be called to acheive the
09500 existence of new, usable information (see the MAIN:EFFECTS part, below).
09600 The WHAT, HOW, and WHY parts are mainly for the user's
09700 benefit.
09800 When a choice between BEINGs must be made, the WHEN,
09900 AFFECTS, and COMPLEXITY-VECTOR parts are queried.
10000 If a new,
10100 manipulated version of the BEING must be created, the
10200 SPECIALIZATIONS, ENCODABLE, DATA-STRUCTURE, PREDICATE, and
10300 FORM-CHANGING parts might be relevant.
10400 If the BEING fails, some
10500 BEING specified in the ALTERNATIVES or GENERALIZATIONS parts might
10600 be tried.
10700 In the current case, the COMPLEXITY-VECTOR says that it is of
10800 average difficulty to call, its descendants may (.5 chance) call it
10900 back, it has an average chance of success and cost of attempting it,
11000 and there is no (.1) good reason to defer it any longer.
11100 The AFFECTS part of the OBTAIN-USABLE-INFORMATION BEING is
11200 clear. CHOOSE-FROM is definitely called, and four others might be.
11300 The absence of some parts, like DATA-STRUCTURE, PREDICATE,
11400 and NLAMBDA, indicates that these qualities don't apply. The absence
11500 of other parts, like SPECIALIZATIONS and ALTERNATIVES, indicates
11600 only a
11700 lack of thoroughness in filling out unneeded BEING parts.
11800 The META-CODE says to choose from the following four
11900 alternatives, each of which is itself a BEING:
12000 Get-Brand-New-Information (in English, from the user), Translate
12100 something (transform from English to BEING-calls),
12200 Analyze-The-Implications (of some existing, translated information),
12300 Extract-a-Relevant-Subset (of the existing information) to
12400 concentrate upon.
12500 SATISFY is usually employed when the BEING doesn't know exactly
12600 which BEING to call. If the ⊗4set⊗* of possible choices is known, as
12700 in this case, then CHOOSE-FROM may be called with the explicit choice set.
12800 Below are exhibited the actual representation of this BEING
12900 in PUP6, and the function which would be executed if it were
13000 ⊗4called⊗*.
13100
13200 .BEGIN NOFILL
13300 .SELECT 6
13400
13500
13600 ⊗4↓_PART_↓ ↓_actual value of the part for OBTAIN-USABLE-INFORMATION BEING_↓⊗*
13700
13800 IDEN ((if you see: (OBTAIN-USABLE-INFORMATION any1)
13900 then return: (OBTAIN-USABLE-INFORMATION (TRANSLATE any1)))
14000 (if you see: (FIND OUT MORE ABOUT any1)
14100 then return: (OBTAIN-USABLE-INFORMATION any1)))
14200 EXPLICIT-ARGS (U)
14300 WHAT ( OBTAIN SOME INFORMATION WHICH CAN BE USED)
14400 HOW ( OBTAIN NEW FACTS ABOUT OLD INFORMATION, OR OBTAIN TOTALLY NEW INFORMATION)
14500 WHY ( PUP HAS NO MORE INFORMATION THAT IT CAN USE TO PROGRESS)
14600 WHEN ((if T then add in -10 because (THIS IS AN EXPONENTIALLY-GROWING, BAD THING TO DO IN GENERAL))
14700 (if NEW-INFO-LIST then add in 111
14800 because (WE SHOULD WORK ON UNASSIMILATED NEW INFORMATION IF THERE IS ANY)))
14900 META-CODE (DO
15000 (CHOOSE-FROM ((TRANSLATE U)
15100 (GET-NEW-INFORMATION U)
15200 (ANALYZE-IMPLICATIONS U)
15300 (EXTRACT-RELEVANT-SUBSET U)))
15400 BECAUSE
15500 (WE CAN ONLY TRY TO OBTAIN USABLE INFORMATION IN ONE WAY AT A TIME))
15600 MAIN-EFFECTS ((to get (NEW INFO any1) do (OBTAIN-USABLE-INFORMATION any1))
15700 (to get (USABLE INFO any1) do (OBTAIN-USABLE-INFORMATION any1)))
15800 AFFECTS ( (CHOOSE-FROM IS CALLED)
15900 (TRANSLATE POSSIBLY IS CALLED)
16000 (GET-NEW-INFORMATION POSSIBLY IS CALLED)
16100 (ANALYZE-IMPLICATIONS POSSIBLY IS CALLED)
16200 (EXTRACT-RELEVANT-SUBSET POSSIBLY IS CALLED) )
16300 COMPLEXITY-VECTOR (.5 .5 .5 .5 .1)
16400
16500 .END
16600
16700 .ONCE FLUSH LEFT
16800 ↓_3.3. What happens when a BEING is called_↓
16900
17000 When a BEING is ⊗4called⊗*, its parts are assembled into a
17100 function which is then executed. Here is the ⊗4FUNCTIONAL⊗* form of the
17200 OBTAIN-USABLE-INFORMATION BEING:
17300
17400 .BEGIN NOFILL
17500 .SELECT 6
17600
17700 (OBTAIN-USABLE-INFORMATION
17800 (LAMBDA (U FN-VALUE FINAL-CO-REQ)
17900 (PROG1
18000 (AND
18100 (SETQ BEING-STACK (CONS OBTAIN-USABLE-INFORMATION BEING-STACK))
18200 (PUT OBTAIN-USABLE-INFORMATION SPEC-WHY BECAUSE)
18300 (EVERY (APPEND CURRENT-DEMONS USER-INTERRUPT-DEMONS)
18400 (QUOTE APPLY*))
18500 (SETQ BECAUSE
18600 (QUOTE (WE CAN ONLY TRY TO OBTAIN USABLE
18700 INFORMATION IN ONE WAY AT A TIME)))
18800 (CHOOSE-FROM (QUOTE ((TRANSLATE U)
18900 (GET-NEW-INFORMATION U)
19000 (ANALYZE-IMPLICATIONS U)
19100 (EXTRACT-RELEVANT-SUBSET U)))))
19200 (SETQ BEING-STACK (CDR BEING-STACK)))))
19300 .END
19400 .SKIP TO COLUMN 1
19500
19600 The process of assembling the BEING parts into a function is
19700 straight-forward. First, the explicit arguments (those global to the
19800 BEING) are bound. The implicit arguments (those local to the BEING,
19900 like PROG variables) are initialized. The name of the BEING is pushed
20000 onto the BEING control stack (pointing to its caller), and any
20100 newly-activated demons are pushed onto the demon stack. The
20200 ARGS-CHECK predicates are evaluated. Then PUP6 works to make each
20300 PRE-REQUISITE true in the world. Each COMMENT is evaluated, then the
20400 CO-REQUISITES, META-CODE, and current demons all are executed in
20500 pseudo-parallel. Each POST-REQUISITE is then satisfied. Since these
20600 activities are all embedded in an AND, any of them may cause the
20700 entire BEING to halt and fail, simply by returning NIL.
20800 In both cases, just before exiting, the demon
20900 stack is popped and the BEING stack is updated (usually just popped),
21000 and control passes to the delegated BEING (usually the one who called
21100 this BEING, at the state when he called it). A fancy context
21200 mechanism was available but not actually needed in PUP6.
21300 The function which assembled all the BEINGs exploited the
21400 fact that it operated only at system load time. Thus if the BEING
21500 had no new DEMONs to activate, all the corresponding demon-stack
21600 manipulations could be omitted. Optimizations like these are clear
21700 from comparing the actual stored parts of OBTAIN-USABLE-INFORMATION,
21800 the description of how it theoretically should be made into a function,
21900 and the actual function form (see above).
22000
22100
22200 .B
22300
22400 .E
22500 .ONCE FLUSH LEFT
22600 ↓_3.4. A high-level, domain-specific BEING_↓
22700
22800 PARTITION-A-DOMAIN is a high-level BEING, specific to the domain of
22900 writing inductive inference programs,
23000 whose basic idea is to divide up a space into categories. Only two
23100 BEING parts are filled in here which were absent from
23200 OBTAIN-USABLE-INFORMATION; namely, SPECIALIZATIONS and DEMONS. The
23300 SPECIALIZATIONS part says that to write a specific version of itself,
23400 a few decisions must be made. The results will then indicate what
23500 pieces of code get assembled together to form the new BEING. The
23600 partition may be only partial (an element of the domain belongs to no
23700 class of the partition), only weak (an element belongs to more than
23800 one class), and, most importantly, the specialized partitioning
23900 BEING should work
24000 by repeatedly doing some of the following three activities: accept a
24100 class-name from the user and guess some of its elements, accept an
24200 element from the user and try to guess which class it belongs to,
24300 or accept an <element, class-name> pair. Other BEINGs know
24400 about these accepting, guessing, and checking activities.
24500 The DEMONS part says that during the partitioning, the only
24600 new demon to keep active is the one called Fringe-of-Consciousness,
24700 which we now illustrate. In the course of
24800 writing GI, the system learns that the main task is one of
24900 grammatical inference. The Grammatical-Inference BEING then asserts
25000 that if the user ever mentions the word TEST, he may actually mean
25100 PARSE. This is placed in the IDEN part of the TEST BEING, and is
25200 therefore only demonized, waiting on the periphery of PUP6's
25300 concentration. It is in fact triggered later in the dialogue, as an
25400 inference surprising to the user.
25500
25600 .BEGIN NOFILL FLUSH LEFT
25700
25800 ↓_3.5. The front and rear parts of the dialogue which results in CF_↓
25900 .END
26000
26100 The dialogue to synthesize CF begins by PUP6 asking the
26200 user for any task. The user replies, ⊗4Write a program which does
26300 concept formation⊗*. There are many decisions that PUP6 knows about in
26400 writing a specialized concept formation program [10],
26500 and it manages to
26600 defer them all. For example, it must choose between classificatory,
26700 comparative, and metrical concept formation. Since all three involve
26800 partitioning a domain of examples, PUP6 decides it can defer this
26900 choice until after code for the partitioning is synthesized. The
27000 effort of the system is now directed toward this "piece" of the
27100 program. When it is completed, an hour or two later, the system asks
27200 the user to make this decision. When he responds ⊗4CLASSIFICATORY⊗*,
27300 which involves ⊗4only⊗* partitioning, the system prints that it has
27400 finished the entire CF task, and dumps the newly created BEINGs onto
27500 a file.
27600
27700 .BEGIN NOFILL FLUSH LEFT
27800
27900 ↓_3.6. Admissability of popular AI language features_↓
28000 .END
28100
28200 The claim is now made that the presence of popular
28300 AI language features do not detract from the combinatorial behavior
28400 of the system, since BEINGs linearly subsume each mechanaism used.
28500 A ⊗4demon⊗*
28600 in PUP6 is merely a function which gets executed periodically,
28700 and may occasionally trigger a BEING. This could be replaced by a
28800 BEING whose EXPLICIT-ARGS-CHECK part contains the triggering
28900 predicate, and whose META-CODE is simply a call by name directly to
29000 the BEING which is supposed to be activated.
29100 An ⊗4assertion⊗* can be
29200 viewed as a BEING containing only an IDEN part; when the BEING
29300 recognizes a form which matches it, it returns the fully instantiated
29400 assertion.
29500 A ⊗4function⊗* is equivalent to a BEING with only META-CODE,
29600 ARGS, and NLAMBDA
29700 parts; one knows almost nothing about it before executing it.
29800
29900 .NOFILL
30000
30100 ↓_3.7. CF: the concept formation target program_↓
30200 .FILL
30300
30400 CF should operate by repeatedly scanning a scene and trying to name it. The
30500 scene is broken into a set of features and a set of objects. Each
30600 feature is a relation
30700 on one or more objects in the scene. Internally, the program
30800 maintains a model for each differently-named
30900 structure it has ever encountered.
31000 The model contains a description of the objects expected in the
31100 scene, a set of features which must be present in the scene (else it
31200 can't be the same as this concept), a set of features which must not
31300 be present in the scene, and a set of features which may or may not
31400 be present. Thus a model is an archtypical scene plus a name.
31500 Each time the program is confronted by a new scene, the program must
31600 scan its models until it finds one which matches it. A model is said
31700 to match a scene if all the MUST features associated with that model
31800 are present in the scene, and all the MUSTNOT features are
31900 absent from the scene. CF
32000 informs the user of this guess,
32100 and accepts the proper concept name. If it guessed incorrectly, it
32200 modifies its models. The wrong guess model may have features added to
32300 its MUST or MUSTNOT sets; the correct concept name model may have to
32400 be modified or (if it's a new concept) created and inserted into the
32500 list of models. For more details, see [2].
32600
32700 .NOFILL
32800
32900 ↓_3.8. A dynamic example_↓
33000 .FILL
33100
33200 An example of the PUP6 community of BEINGs interacting will now
33300 be presented.
33400 When a BEING is said to do or recognize or know something, as
33500 in the following paragraphs, what is actually meant is
33600 that one or more of its parts specificly encode that knowledge. All
33700 the parts of the hundred BEINGs in PUP6 were coded by hand, not by
33800 each other. They then encoded other BEINGs, interacting only via
33900 the dialogue.
34000 Let's jump one third of the way into the dialogue which
34100 writes CF. The system learns it must compare the input scene against
34200 its internally stored models of concepts, until it finds one which
34300 doesn't fail the comparison. It asks the user what it means for
34400 scene S to fail the comparison to model M. The user replies,
34500 whenever M is incompatible with the observed features of S.
34600 The IDEN part of the
34700 CONTRADICTS BEING recognizes this sentence pattern, and transforms it
34800 to
34900 .NOFILL
35000 (FORSOME F IN M-FEATURES (specialized:contradicts F S-FEATURES)).
35100 .FILL
35200 The BEING
35300 which inserts this into the synthesized code requires that the user
35400 pick some proper name for the function specialized:contradicts;
35500 this will be a streamlined contradiction test written by the
35600 CONTRADICTS BEING. Say the user reponds by calling it IMPOSS. This naming
35700 and specializing is central to BEING creation: a BEING recognizes an
35800 instance of itself, and decides either to insert a call to itself or
35900 else to insert a call to a specialized version of itself. If any
36000 nontrivial decisions must be made, and can be settled at synthesis
36100 time, then the latter alternative is chosen. CONTRADICTS is too
36200 general a BEING to be called in an inner loop, so its content will
36300 be hammered out at synthesis time. On the other hand,
36400 FORSOME is so primitive that no specialized
36500 version of it is written normally.
36600 Here is the way this piece of the dialogue actually appears.
36700 The user's reponses are italicized.
36800 .BEGIN NOFILL FLUSH LEFT
36900
37000 PUP: Please type in a logical expression which is true iff we terminate the loop
37100 USER: ⊗4(Any feature in model-features is incompatible with scene-features)⊗*
37200 PUP: PUP wants USER to type in name for specialized version of CONTRADICTS
37300 USER: ⊗4IMPOSS⊗*
37400 .END
37500 Later in the dialogue, PUP6 decides it must
37600 expand the function IMPOSS. The CONTRADICTS BEING is again called on; this
37700 time it is asked how to write a specialized version of a
37800 contradiction test. It replies that SOME-OF the following types of
37900 contradiction may occur: PROBABILITY=0, PROBABILITY=1, and
38000 PROBABILITYε(0,1). This is the germ of the idea for the
38100 MUSTNOT/MUST/MAY categorization of features. The SOME-OF BEING takes
38200 control, and asks if the decision can be deferred. The DEFERRAL
38300 BEING looks about, first asking if there is any non-null piece of
38400 code that all three have in common. This fails, and eventually the
38500 DEFERRAL BEING reports failure. SOME-OF sees it has no basis upon
38600 which to form a guess, and wants somebody to ask the user. The
38700 ASK-USER BEING takes over, and trivially finds out what exactly it is
38800 that PUP6
38900 wants to learn. The names of the three choices are so cryptic that
39000 their WHAT and HOW parts are printed out to the user, as well as
39100 their names. The user types back his choices, in our case all three.
39200 SOME-OF composes three new function calls, separated by a
39300 conditional:
39400 .BEGIN GROUP NOFILL SELECT 3 INDENT 0
39500
39600 (COND ((IS-OF-TYPE F PROBABILITY=0-PART-OF-M-FEATURES) (PROBABILITY=0-CONTRADICTION F S-FEATURES))
39700 ((IS-OF-TYPE F PROBABILITY=1-PART-OF-M-FEATURES) (PROBABILITY=1-CONTRADICTION F S-FEATURES))
39800 ((IS-OF-TYPE F PROBABILITYε(0,1)-PART-OF-M-FEATURES) (PROBABILITYε(0,1)-CONTRADICTION F S-FEATURES)))
39900 .END
40000 TRICHOTOMY recognizes this as a split on a function's values
40100 being =0, =1, or between zero and one. It asks whether this
40200 particular function can only range over the interval [0,1].
40300 PROBABILITY answers affirmatively, so SOME-OF replaces the final
40400 IS-OF-TYPE test by the constant T. Later on, PUP6 must worry about
40500 the other two tests, and about the three contradiction predicates.
40600 These latter entities know (their ENCODABLE parts tell them) that
40700 they are immediately encodable. A probability=0 contradiction means
40800 that arg1 must not occur in the world arg2 yet it does. So the
40900 META-CODE of the PROBABILITY=0-CONTRADICTION BEING is defined as
41000 (MEMBER arg1 arg2). This corresponds to a MUSTNOT feature F which is
41100 present in the world (in
41200 the set S-FEATURES, features of the scene). A
41300 probability=1 contradiction occurs when a feature arg1 must occur in
41400 the world arg2, yet it doesn't. So its definition is simply (NOT
41500 (MEMBER arg1 arg2)). It is impossible for a feature with probability
41600 in (0,1) to be in contradiction with any world (lacking negated
41700 features), so this third predicate is defined as the constant NIL.
41800 That is, if F is a MAY feature of the model M, then there can be no
41900 contradiction between F and ⊗4any⊗* features of the scene S.
42000 The IS-OF-TYPE BEING recognizes that it must work hard to
42100 replace each of the two case tests, unless M-FEATURES is organized
42200 permanently into three parts (thus permitting the complex function
42300 "IS-OF-TYPE" to be replaced by the simple one "MEMBER" in the above
42400 piece of code). The STRUCTURE-INDUCING BEING will take over, to probe
42500 the permissability and the difficulty of such a constraint. It finds
42600 nothing about this tripartite structuring which could damage any
42700 earlier synthesized code, and asks the user's blessing. Notes are
42800 added to the list of coding warnings, stating that any reference to
42900 the entire list of M-FEATURES must be replaced by either APPEND of
43000 the three new lists, or else by three separate statements. GET-NAME
43100 is indirectly called, and he has the user name the three new sets of
43200 features; say he responds by calling them MUSTNOT, MUST, and MAY. The
43300 system would at this point say to draw an arrow on its graph of newly
43400 created BEINGs, going
43500 from the function call (IMPOSS F S-FEATURES) to the new block of code:
43600 .BEGIN GROUP NOFILL INDENT 0 SELECT 8
43700
43800 (COND ((MEMBER F MUSTNOT-PART-OF-M) (MEMBER F S-FEATURES))
43900 ((MEMBER F MUST-PART-OF-M) (NOT (MEMBER F S-FEATURES)))
44000 ( T (COMMENT THIS "T" REPLACES "MEMBER F MAY-PART-OF-M") NIL))
44100 .END
44200 This is now the META:CODE part of the new BEING called IMPOSS.
44300 Most of the other parts are taken from its generalization, namely
44400 CONTRADICTS. During the course of writing this piece, however, some
44500 of these parts should be slightly changed. For example, its reason
44600 for existing should be strengthened when the simple MEMBER function
44700 calls replaced the slow IS-OF-TYPE BEING calls.
44800 Most of this processing is inter-BEING activity; the user is
44900 not needed for -- or even informed of -- most of it.
45000 He has the feeling
45100 of merely directing, constraining, and watching the activities of a
45200 busy programmer. Unfortunately, "the user" is not generic; there
45300 was only one successful user. PUP6 insists
45400 on doing structured programming, so its traces are superficially
45500 similar to macro expansion. Despite this concentration on planning,
45600 no BEINGs system
45700 should halt so long as any details remain.
45800
45900 .B
46000
46100 .E
46200 .ONCE FLUSH LEFT
46300 ↓_3.10. Excerpt from the synthesized program itself running_↓
46400
46500 The PUP6 system interacts with the user, resulting in the creation of
46600 CF, the desired target program. Like PUP6, CF is nothing but a pool of
46700 BEINGs. So, as it runs, the user can interrupt it and ask it questions
46800 about what it's doing. The answers are typically just some parts of the
46900 BEING currently in control. An excerpt of CF running without interruption
47000 is given below, followed by the same piece with interruptions.
47100 The user's responses are in italics. ⊗4α:⊗*
47200 signifies he has interrupted,
47300 and ⊗4β.⊗* signifies he has told PUP6 ⊗4OK, go back to work now.⊗*
47400 Some liberty has been taken with the
47500 English; e.g., the user really types ⊗4WHAT?⊗*, not ⊗4What are you doing?⊗*
47600 .BEGIN NOFILL FLUSH LEFT
47700
47800 READY TO ACCEPT BRAND NEW SCENE: ⊗4(??? (A B) (BLOCK A) (GREEN B))⊗*
47900 NOT AN ARCH. NOT A TOWER. MIGHT BE A ROW. MY GUESS IS ROW.
48000 WHAT IS IT REALLY? ⊗4NOTHING⊗*
48100 TRANSFER FROM MAY TO MUST SETS OF ROW: (TOUCH A B)
48200 READY TO ACCEPT BRAND NEW SCENE:
48300
48400 Here is the same excerpt, but with the user interrupting occasionally:
48500 ⊗4α: What are you doing?⊗*
48600 PUP: Divide a domain into subdomains, using specialized version of PARTITION-DOMAIN
48700 ⊗4How?⊗*
48800 PUP: By building up the partition gradually, by adding one <scene, name> pair
48900 ⊗4OK. Go back to work⊗*
49000
49100 READY TO ACCEPT BRAND NEW SCENE: ⊗4(??? (A B) (BLOCK A) (GREEN B))⊗*
49200
49300 ⊗4α: What are you doing?⊗*
49400 PUP: Break a piece off (??? (A B) (BLOCK A) (GREEN B)) to examine
49500 ⊗4What is the meta-code of the current BEING?⊗*
49600 PUP: The meta-code of SOME-PART-OF (version 14) is (CAR arg1) ⊗4β.⊗*
49700
49800 NOT AN ARCH.
49900 ⊗4α: Why?⊗*
50000 PUP: The ARCH MUST relation (SUPPORTS A B) is contradicted in the SCENE ⊗4β.⊗*
50100
50200 NOT A TOWER. MIGHT BE A ROW. MY GUESS IS ROW.
50300 WHAT IS IT REALLY? ⊗4α: Why are you asking?⊗*
50400 PUP: PUP cannot resolve it, and must at this time, so PUP asks USER
50500 ⊗4OK. What you wanted is: NOTHING
50600
50700 α: What are you doing?⊗*
50800 PUP: Go through space of concept names, and make user aware of changes
50900 ⊗4What BEINGs might this affect?⊗*
51000 PUP: MESSAGE is possibly called; some version of TEST is possibly called ⊗4β.⊗*
51100
51200 TRANSFER FROM MAY TO MUST SETS OF ROW: (TOUCH A B)
51300 READY TO ACCEPT BRAND NEW SCENE:
51400
51500
51600 .END
51700 .ONCE FLUSH LEFT
51800 ↓_3.10. BEINGs applied to volleyball and mathematics_↓
51900
52000 Since the only existing BEINGs system does automatic programming,
52100 it is excusable to concentrate on that task. Let us briefly digress,
52200 however, to indicate how a community of BEINGs could do other activities.
52300 Consider first the simulation of a volleyball game. A
52400 BEINGs-based system might create a specialized BEING for each player,
52500 perhaps with a complexity vector indicating his abilities, reflexes,
52600 etc. The BEING in control would be the player hitting the ball. A
52700 specialized Choose-from BEING would decide who goes next,
52800 occasionally interpreting a tie between BEINGs vying for control as a
52900 collision on the court.
53000 A less bizarre enterprise for BEINGs
53100 is the understanding of mathematics.
53200 Such a project is now in progress at SAIL, encompassing
53300 learning, discovery, and intuition, in several domains of mathematics.
53400 The driving force in such a system is aesthetic: the desire to complete each
53500 BEING. Since the task is no longer to write programs, a different set
53600 of BEING parts is called for. For efficiency, the guidance strategies
53700 might be implemented as rules. There would be a BEING for each entity,
53800 be it object, operator, analogy, etc. Its parts might be as follows:
53900 .NEXT PAGE
54000 .BEGIN NOFILL FLUSH LEFT
54100
54200 ⊗2DEFINITIONS⊗* Several equivalent definitions
54300 ⊗2NAME⊗* Significant English variations
54400 ⊗2IDEN⊗* Tests to see if this operator is the one being referred to
54500 ⊗2NOT-IDEN⊗* Tests to see if this operator is irrelevant
54600 ⊗2QUICK-IDEN/NOT-IDEN⊗* Cheap tests to see if operator is/isn't relevant
54700 ⊗2EXAMPLES⊗* Includes trivial, typical, and advanced cases; non-examples
54800 ⊗2BOUNDARY⊗* Examples which characterize the limits of this concept
54900 ⊗2FIX-BOUNDARY⊗* How can you change a concept so it crosses this border?
55000 ⊗2IMAGE⊗* Analogic interpretations: ties to simpler concepts, to real-world
55100 ⊗2WHY⊗* Why is this worth naming as a separate BEING?
55200 ⊗2USE⊗* Where is this used frequently, to advantage?
55300 ⊗2GENERALIZATIONS⊗* What is this a special case of? The new features
55400 ⊗2SPECIALIZATIONS⊗* What are special cases of this? What is simplified?
55500 ⊗2REPRESENTATION⊗* How should this be represented internally?
55600 ⊗2TIES⊗* What other objects and operators are associated with this concept?
55700 ⊗2RESTRICTIONS⊗* What can't it do, or one do to it? Temporary?
55800 ⊗2VALUE⊗* Aesthetic worth, efficiency ratings, complexity, certainty, ubiquity
55900 ⊗2EFFECTS⊗* The range for an operator, the results of using this concept
56000 ⊗2VIEWS⊗* How to view as an operator, property, set, object, relationship
56100 ⊗2HANDLES⊗* How to compute (get a handle on) this concept
56200
56300 .END
56400
00100
00200 .B
00300
00400 .E
00500 .ONCE CENTER
00600 ⊗5↓_4. Automatic Programming Task_↓
00700
00800 After the target concept formation program was specified, it
00900 was trimmed and then rewritten as a structured program [11]. Next,
01000 a complete dialogue was simulated between the user and a human
01100 programmer (referred to as the system-player) playing the role of an
01200 "intelligent" automatic programming system (similar to, e.g.,
01300 [12]). The system-player kept careful records as he
01400 programmed, and tried to create a bug-free structured program. The
01500 dialogue was then annotated: after each user response, comments
01600 were inserted which described the "states" the system-player had gone
01700 through before printing his next response. This included blind paths
01800 which were tried, use of outside world knowledge, and, in general,
01900 was meant to be the "intelligence" necessary to do the task. The
02000 fear was that a system could be built which synthesized the concept
02100 formation program, and yet was so unintelligent that nothing was
02200 learned from it. (see section 4.1 on PW1, for example, in [13]).
02300 Hopefully, any system which
02400 (i) got the target program correctly,
02500 (ii) followed this
02600 initial dialogue, and, most importantly, (iii) went
02700 through the same line of reasoning that the comments indicated the
02800 system-player
02900 followed, would be far along the road toward intelligence. A
03000 corollary of this incremental annotated protocol approach is that the
03100 abilities of the user must coincide with those of the subject who
03200 participated in the protocol. The system would be
03300 far along the road toward automatic programming if it also (iv) was
03400 able to write CF from several dialogues, from several users, with
03500 little preparation. PUP6 was not designed to do this, and in the end
03600 it proved to be a serious deficit. Henceforth, ⊗4protocol⊗* will
03700 refer to this user-player / system-player simulated dialogue.
03800
03900 At this point, a rough
04000 initial set of BEINGs surfaced. Each one had not
04100 much more than a name and a vague description of what it must do.
04200 The dialogue was cycled through again, painstakingly, and the
04300 comments were replaced by a description of which BEINGs would call
04400 which other BEINGs, why, and the results of each such call. The
04500 constraints on each BEING thus grew, sometimes changed, and
04600 occasionally a new BEING or BEING part had to be added to the
04700 design. This process produced a long
04800 hand trace of the system execution.
04900 About eighty BEINGs were needed: a dozen domain-specific ones and
05000 the rest domain-independent programming knowledge.
05100 A result of this method of incremental specification of
05200 BEINGs was that each BEING had only those parts which were going to be
05300 used sometime during the ensuing dialogue. This seemed too specific,
05400 so some effort was spent filling out parts that weren't strictly
05500 necessary to write the concept formation program. Perhaps more
05600 careful attention to this activity would have made the system more
05700 tolerant of changes in the dialogue.
05800 Good measures of concentration of intelligence are not yet
05900 available. The only alternative is to present ephemeral numerical
06000 efficiency data, which now follows. PUP6 is 200 pages long when
06100 PRETTY-PRINTED, and has synthesized three LISP programs, 7, 20, and 30
06200 pages long (1, 4, and 6 pages, when coded by hand).
06300 PUP6 takes 60 cpu minutes to produce CF (compiled INTERLISP
06400 code, run on a PDP-10 TENEX system). During this time,
06500 300K characters get typed out to the user, who reponds with about
06600 4K himself.
06700 The mean wait time (between
06800 the user's input and the next machine output) is several seconds. The
06900 longest delay between successive user inputs is 1 CPU minute.
07000
00100
00200 .B
00300
00400 .E
00500 .ONCE CENTER
00600 ⊗5↓_5. Conclusions_↓
00700
00800 While the exact number of BEING parts is unimportant, its magnitude
00900 (a few tens) may be relevant to the feasability of BEINGs systems.
01000 If it were ~1, any uniform representation (e.g., predicate calculus)
01100 would be as easy to use; if it were ~1000, the task of creating
01200 the original pool of BEINGs would be too formidable and ill-structured.
01300 The number of BEING parts is therefore a parameter
01400 expressing the degreee of compromise between structure and standardization
01500 in the community of BEINGs.
01600
01700 The location of relevant information is
01800 effected by giving each BEING the responsibility
01900 for recognizing when it is talked about. This distributed activity beats
02000 the exponential nature of this problem,
02100 iff the computer used has as many processors as
02200 there are BEINGs.
02300
02400 The only startling result was the "inteligent" style of the generated code.
02500 As shown in section 3.9, the synthesized programs can be interrupted
02600 and queried as they
02700 run.
02800
02900 The set of questions the user was expected to want to ask is similar to the
03000 set of questions one BEING can ask another: the BEING parts. When a "nice"
03100 user interrupts, his question is answered by a simple retrieval. Real
03200 users were seldom nice; PUP6 often misunderstood what was asked.
03300
03400 To modify PUP6 to synthesize programs in a domain other than inductive
03500 inference, it would be necessary to add a few domain-independent BEINGs
03600 and several domain-specific ones, and to generalize some parts of some
03700 existing BEINGs.
03800 The second and third target programs were attempted to determine just
03900 how difficult this task is.
04000 In fact, most of the existing BEINGs ⊗4were⊗* used in generating those
04100 new target programs.
04200 Although only a few new BEINGs were
04300 needed, they could not have been added by an untrained user. Also, the
04400 dialogues were not well-suited to their tasks (since the communication
04500 subsystem was generated from a concept-formation protocol) and were
04600 quite brittle.
04700
04800 There was no sophistocated user model, and this caused the entire
04900 system to suffer. The BEINGs didn't have any indication of how
05000 verbose they were in toto. Swamping the user with unneeded detail
05100 also increases his chances of erring. It became necessary to
05200 insert a FORGETFUL-USER demon, to prevent, e.g., delayed anaphora.
05300 Related to this is the problem of keeping the human user oriented.
05400 PUP6 used the obvious scheme (cursors pointing into a graph of the
05500 newly created BEINGs), which was insufficient. The user often wished
05600 to refer to a section not by name or by pointing, but rather by some
05700 brief, descriptive, meaningful (to him only!) phrase.
05800
05900 The design of BEINGs is toward large programs; low-level, efficient
06000 code could be turned out as a ⊗4simulation⊗* effort, much as playing
06100 volleyball. The analogue is using a high-level
06200 language to turn out efficient machine code.
06300
06400 Some of the BEING parts proved unnecessary. The CO-REQUISITES part was
06500 never used: the only simultaneous activity needed was demon
06600 activiation. The AFFECTS part was of occasional interest to the user,
06700 but not really used by any BEINGs. The EFFECTS part originally had a
06800 twin, describing what would happen if the BEING were ⊗4not⊗*
06900 executed then. In each case, this turned out to be merely a
07000 restatement of the frame problem.
07100
07200 The idea of a universal set of BEING parts (for a given system) fared
07300 marginally well. Each part was used in about a third of all BEINGs,
07400 and each BEING used about a third of all possible parts. If these
07500 fractions had been much lower, the advantage of uniformity would
07600 have vanished. The future of BEINGs (e.g., in the current
07700 math-understanding project) seems to be as a tool, a single aspect of
07800 the system.
00100 .BEGIN INDENT 0
00200
00300 ↓_6. References_↓
00400 .SELECT 1
00500 .SPACING 30 MILLS
00600 .PREFACE 100 MILLS
00700
00800 [12] Balzer, Robert, AIRLINE reserv. study..., 197..
00900
01000 [11] Gadwa, Peter, ⊗4SPOT, a mini concept formation program⊗*,
01100 Unpublished Master's Thesis, Artificial Intelligence Laboratory,
01200 Stanford University, Stanford, California, August, 1973.
01300
01400 [13] Green et al.,
01500 ⊗4Progress Report on Program-Understanding Systems⊗*, Memo AIM-240,
01600 CS Report STAN-CS-74-444,Artificial Intelligence Laboratory,
01700 Stanford University, August, 1974.
01800
01900 [10] Hempel, Carl G., ⊗4Fundamentals of Concept Formation in
02000 Empirical Science⊗*, University of Chicago, Chicago, Illinois,
02100 1952.
02200
02300 [1] Hewitt, Carl, ⊗4A Universal Modular ACTOR Formalism for
02400 Artificial Intelligence⊗*, 3rd International Joint Conference on
02500 Artificial Intelligence,
02600 1973, pp. 235-245.
02700
02800 [8] Kay, Allen, ⊗4CLASSes paper⊗*, ...
02900
03000 [9] Minsky, Marvin, ⊗4Frames⊗*, in ⊗4Psychology of Computer
03100 Vision⊗*, 1974.
03200
03300 [4] McCarthy, John,and Hayes, P., ⊗4Some Philosophical
03400 Problems From the
03500 Standpoint of Artificial Intelligence⊗*, Machine Intelligence 4,
03600 pp. 463-502.
03700
03800 [5] Minsky, Marvin, and Papert, Seymour, ⊗4Artificial
03900 Intelligence Progress Report⊗*, MIT Project MAC, AI Memo
04000 252, 1972.
04100
04200 [3] Newell, Allen, and Simon, Herbert,
04300 ⊗4Human Problem Solving⊗*, 1973.
04400
04500 [6] Teitelman, Warren, ⊗4INTERLISP Reference
04600 Manual⊗*, XEROX PARC, 1974.
04700
04800 [2] Winston, Patrick, ⊗4Learning Structural Descriptions
04900 from Examples⊗*, Ph.D. thesis, Dept. of Electrical Engineering,
05000 TR-76, Project MAC, TR-231,
05100 MIT AI Lab,
05200 September, 1970.
05300
05400
05500 The ideas and the system described use concepts from ACTORS,
05600 heterarchy, structured programming, assertional data bases,
05700 flexible data types, pattern-directed invocation of procedural
05800 knowledge, the paradigm of dialogue, studies on program specification,
05900 QLISP, INTERLISP, LISP, English, ... In particular, the author
06000 drew heavily from creative discussions with C. Green, R. Waldinger,
06100 D. Barstow, B. McCune, D. Shaw, E. Sacerdoti, and L. Steinberg.
06200 .END